This invention relates to methods of operating digital computers to perform heuristic searches, and more particularly, to a system and method for solving combinatorial optimization problems.
Practical enumerative search or combinatorial optimization problems occur in a variety of fields including scheduling, routing, design layout, engineering disciplines, management and econometrics. Solutions to these problems are characterized by identifying an optimum combination of individual choice selections from among a multitude of possibilities. Examples of such enumerative search, graph search, or combinatorial optimization problems include moves in board games such as chess or go, determining how articles of different sizes can be packed in containers of limited capacity, determining optimum scheduling of operations in a manufacturing process, and capacitated vehicle routing with time windows.
Enumerative search, or combinatorial optimization problems is a well established field, for example, see Aho et al. in xe2x80x9cData Structures and Algorithms,xe2x80x9d Addison-Wesley Reading, 1983. In principle, combinatorial optimization problems can be solved by testing all possible combinations of choices and selecting only those combinations that give the most favorable result. However, other than in simple problems, the number of possible combinations rapidly becomes so large that, even when digital computers are employed, the solution of a single problem on a single processor may take hours, days, sometimes even months or years.
In the prior art, the time required to solve combinatorial optimization problems has been reduced by using efficient heuristic methods that are not guaranteed to find an optimal solution, but one that is near optimal. Typical heuristic methods combine some form of gradient-descent search to find local optima with some strategy for escaping non-optimal local optima. For to example, annealing resolves the problem of getting stuck in local optima by allowing xe2x80x9cmovesxe2x80x9d to inferior solutions. By letting the minimizing heuristic accept occasional uphill moves, the heuristic can escape from a local optimum xe2x80x9cgullyxe2x80x9d and eventually fall into a possible xe2x80x9cvalleyxe2x80x9d to find a global optimum. The probability to go back, that is, moving uphill, decreases with time, and the heuristic will finally xe2x80x9cfreezexe2x80x9d in a local optimum. However, these systems do not have any performance guarantees, and may often return solutions that are far from optimal.
One idea for improving the performance of search techniques for combinatorial optimization problems is to involve the human user in the search process via a cooperative interface technique. A specific technique that does this is called interactive evolution. Because cooperative interface paradigms like interactive evolution have been used mostly for designing various kinds of computer graphics, these are best characterized in terms of a design process rather than an optimization process. Generally, interactive-evolution systems generate successive sets of designs, based on previous designs, and a user selects which designs to accept for further refinement, and which to reject. Thus, designs evolve, subject to user-supplied selection criteria, see Kochhar et al. in xe2x80x9cUser control in cooperative computer-aided design,xe2x80x9d Proceedings of the 1990 ACM SIGGRAPH Symposium on User Interface Software and Technology, pp. 143-151, 1990.
Constraint-based interfaces constitute yet another human-computer cooperative technique for design/optimization tasks. These are popular in drawing applications, see Nelson et al. in xe2x80x9cThe Juno-2 Constraint-Based Drawing Editor,xe2x80x9d Digital Equipment Corp. SRCxe2x80x94Research Report 131a, 1994. Typically, the user imposes geometric or topological constraints on a nascent drawing such that subsequent manipulation is constrained to useful areas of the design space.
The invention provides a cooperative-interface technique that partitions combinatorial optimization problems into two tasks, one for the user and one for the computer processor, to facilitate a human-guided search. The processor is only responsible for finding local optima using, for example, a hill-climbing search which can be either greedy (best first) or steepest ascent (shortest). The result of the search is visualized, and the user identifies promising regions of the search space for the processor to explore. The user can also intervene to help the processor escape non-optimal local optima, or change the constraints of the optimizing function. The general strategy combines heuristic-search and information-visualization techniques in an interactive system. In a specific application, the invention is applied to the problem of capacitated vehicle routing with time windows (CVRTW).
More specifically, the invention provides a system and method that enables an interactively guided heuristic search for solving a combinatorial optimization problem. The system initially performs a greedy hill-climbing search to obtain an initial solution to a combinatorial optimization problem using initial default parameters for the search process.
The initial solution and the combinatorial optimization problem are visualized on an optimization table, a table-top display device that is suitable for group viewing and interaction. The parameters of the search process are then altered by the user based on a visualization of the combinatorial optimization problem and the initial solution. Then, the searching, visualizing, and parameter setting are repeated until the current solution is selected as an acceptable solution of the combinatorial optimization problem is by the user. The term xe2x80x9cacceptablexe2x80x9d is used here instead of xe2x80x9coptimalxe2x80x9d because the user can certainly accept a less than xe2x80x9coptimalxe2x80x9d solution based on facts and conditions known only to the user. Potentially, these facts and conditions could be impossible to duplicate in a pure process driven search to determine an optimal solution.
During the repeating, the search-process parameters can be a set of probabilities, if the search is a random perturbation-based search. Alternatively, the search-process parameters can be a set of priorities, if the search is an exhaustive local search.